1. Field of the Invention
This invention relates to software testing and verification in general and more particularly to determining dynamic properties of programs.
2. Description of the Prior Art
Introduction
When developing large programs, it is often important to have knowledge about dynamic properties: properties that can be determined only by running the program. Often, the dynamic properties involve information that is not visible during the normal operation of the program. Examples of such dynamic properties with respect to a program P and a set of inputs I for the program are:
1. When run with inputs I, does P execute all its functions? PA1 2. When run with inputs I, does P execute all its IF-statements in both directions? PA1 3. When run with inputs I, does it ever happen that the pointer variable aPerson, which is known be of type struct person * ever point to an object which is not of type struct person?
In order to make the above information and other information like it externally visible, the program needs to be instrumented in some way so that it when the program is executed, it produces output containing the desired information.
The prior art has developed a number of ways of instrumenting a program. One class of these ways adds instrumentation during the process of building the program, that is, the process of compiling the source code to produce object code. One of the ways that belongs to this class is simply adding code for the instrumentation to the source code and then compiling the source code to produce the object code. The object code of course contains code corresponding to the instrumentation code which was added to the source code. Another way is to compile the source code using a special compiler which adds the necessary instrumentation to the object code.
The first technique, adding instrumentation code to the source code, is very general; the kinds of instrumentation which can be added are limited only by the ingenuity of the programmer. The disadvantage, of course, is that adding the instrumentation has meant changing the source code; thus, the source code being investigated is no longer the original source code. The second technique does not require changing the source code, but is considerably less general; only those kinds of instrumentation can be added which are provided by the particular special compiler. Other types of instrumentation require other special compilers or even modification of one of the existing special compilers. Examples of such special compilers are lcc or cc -p, available on computer systems operating under the well-known UNIX operating system (UNIX is a registered trademark of XOPEN).
All of the techniques for instrumenting a program when it is built suffer from the difficulty that the building process can be very complex, and it is often difficult to ensure that the instrumented version of the program built by the build process is functionally equivalent to the version which the build process builds for customers.
Another class of techniques uses tools for instrumenting the object code of a program after the program has been built. An example of such a tools is PURIFY, sold by Pure Software, Inc., 1309 S. Mary Ave., Sunnyvale, Calif., which exploits special patterns of machine code sequences and compiler code generation techniques to identify locations in the binary that are relevant to the property being investigated. The disadvantages of tools like PURIFY are that each tool permits investigation of a small fixed set of properties and that there is no portability, since a version of the tool is required for each different class of processor.
FIG. 1 provides a conceptual overview of systems of the type just described. Under normal circumstances, a system 102 of one or more programs runs with inputs 101 in an execution environment 104. Under these conditions, an internal property such as "does this system execute all functions on inputs 101" cannot be determined. To determine the internal property, we build a transformed version of the system 105, which has been instrumented to generate side effects when something happens during an execution of system 102 which is relevant to the desired property.
For instance, if one wants to find out if system 102 executes all of its functions when executed with inputs 101, one can instrument system 102 by inserting a print statement at the beginning of the source code for each function called by system 102. The instrumentation transforms system 102 into system 105. Now this transformed system 105 is run on inputs 101. Each time transformed system 105 executes a function, it executes the print statement which was inserted at the beginning of the function. The execution of the print statement is a side effect 106, and by looking at the output from the print statements, the programmer can determine which of the print statements were executed and can use that information to determine which functions were executed.
An example of how source code may be modified to determine test coverage for a given set of test inputs is shown in FIG. 4. In this case, the goal is to determine if the test has caused every if-statement to exercise both its true branch and its false branch. The original source code 401 with an if-statement (true and false branches on lines 2 and 5 respectively) is modified by inserting print statements (402) at lines 1.i and 4.i; when this modified code is executed, messages about branch executions are output to a log file and test coverage can be determined by looking at the messages in the log file.
The above techniques all have important drawbacks. Hand instrumentation is completely flexible, and is limited only by the programmer's ingenuity, but is impractical for large programs. Instrumentation tools are practical for large programs, but each tool only provides a limited variety of instrumentation possibilities, and consequently, instrumentation done with these tools is far less flexible than hand instrumentation.